package cn.edu.njust.alg;

/**
 * 创建时间：2015年5月25日 下午12:19:32 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Line.java 类说明：
 */

public class Line {
	int left, right, count;
	Line leftchild, rightchild;

	public Line() {

	}

	public Line(int left, int right) {
		this.left = left;
		this.right = right;
		this.count = 0;
		this.leftchild = null;
		this.rightchild = null;
	}

	public static void createTree(Line root) {
		if (root.left == root.right) {
			return;
		}
		int left = root.left;
		int right = root.right;
		int mid = (left + right) / 2;
		Line leftchild = new Line(left, mid);
		Line rightchild = new Line(mid + 1, right);
		root.leftchild = leftchild;
		root.rightchild = rightchild;
		createTree(leftchild);
		createTree(rightchild);
	}

	public static void insertLine(Line root, int left, int right) {
		int mid = (root.left + root.right) / 2;
		if (root.left == left && root.right == right) {
			root.count++;
		} else if (right <= mid) {
			insertLine(root.leftchild, left, right);
		} else if (left > mid) {
			insertLine(root.rightchild, left, right);
		} else {
			insertLine(root.leftchild, left, mid);
			insertLine(root, mid + 1, right);
		}
	}

	public static void inOrder(Line root) {
		if (root == null) {
			return;
		}
		System.out.println("[ " + root.left + " " + root.right + " "
				+ root.count + " ]");
		inOrder(root.leftchild);
		inOrder(root.rightchild);
	}

	public static int getCount(Line root, int n) {
		if (root == null || n < root.left || n > root.right) {
			return 0;
		}
		int mid = (root.left + root.right) / 2;
		int count = 0;
		if (n <= mid) {
			count = getCount(root.leftchild, n) + root.count;
		} else {
			count = getCount(root.rightchild, n) + root.count;
		}

		return count;
	}

	public static void main(String[] args) {
		Line line = new Line(0, 7);
		createTree(line);
		insertLine(line, 0, 7);
		insertLine(line, 2, 5);
		insertLine(line, 4, 6);
		System.out.println(getCount(line, 4));
	}

}
